COMMENT ⊗   VALID 00011 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	\input acphdr % Answer pages (double-check position of figures)
C00004 00003	%folio 795 galley 11b (C) Addison-Wesley 1978	*
C00008 00004	%folio 796 galley 11c (C) Addison-Wesley 1978	*
C00015 00005	%folio 797 galley 12 (C) Addison-Wesley 1978	*
C00025 00006	%folio 800 galley 13 (C) Addison-Wesley 1978	*
C00033 00007	%folio 802 galley 1a (C) Addison-Wesley 1978	*
C00045 00008	%folio 804 galley 1b (C) Addison-Wesley 1978	*
C00049 00009	%folio 805 galley 2 (C) Addison-Wesley 1978	*
C00066 00010	%folio 810 galley 3 (C) Addison-Wesley 1978	*
C00084 00011	%folio 818 galley 4a (C) Addison-Wesley 1978	*
C00100 ENDMK
C⊗;
\input acphdr % Answer pages (double-check position of figures)
\runninglefthead{ANSWERS TO EXERCISES}
\titlepage\setcount00
\null
\vfill
\tenpoint
\ctrline{ANSWER PAGES for THE ART OF COMPUTER PROGRAMMING}
\ctrline{(Volume 2)}
\ctrline{$\copyright$ 1978 Addison--Wesley Publishing Company, Inc.}
\vfill
\eject
\setcount0 1
%folio 795 galley 11b (C) Addison-Wesley 1978	*
\ansbegin{4.6}

\ansno 1. $9x↑2 + 7x + 9$;\xskip $5x↑3 + 7x↑2
+ 2x + 6$.

\ansno 2. (a) True.\xskip (b) False if the algebraic
system $S$ contains ``zero divisors,'' nonzero numbers whose
product is zero, as in exercise 1; otherwise true.\xskip (c) True when $m≠n$, but
false in general when $m=n$, since the leading coefficients might cancel.

\ansno 3. Assume that $r ≤ s$. For $0
≤ k ≤ r$ the maximum is $m↓1m↓2(k + 1)$; for $r ≤ k ≤ s$ it
is $m↓1m↓2(r + 1)$; for $s ≤ k ≤ r + s$ it is $m↓1m↓2(r + s
+ 1 - k)$. The least upper bound valid for all $k$ is $m↓1m↓2(r
+ 1)$.\xskip (The solver of this exercise will know how to factor
the polynomial $x↑7 + 2x↑6 + 3x↑5 + 3x↑4 + 3x↑3 + 3x↑2 + 2x
+ 1$.)

\ansno 4. If one of the polynomials has fewer than
$2↑t$ nonzero coefficients, the product can be formed by putting
exactly $t - 1$ zeros between each of the coefficients, then
multiplying in the binary number system, and finally using a
logical \.{AND} operation (present on most binary computers, cf.\
Section 4.5.4) to zero out the extra bits. For example, if $t
= 3$, the multiplication in the text would become $(1001000001)↓2
\times (1000001001)↓2 = (1001001011001001001)↓2$; if we \.{AND}
this result with the constant $(1001001 \ldotsm 1001)↓2$, the desired
answer is obtained. A similar technique can be used to multiply
polynomials with nonnegative coefficients, when it is known that
the coefficients will not be too large.

\ansno 5. Polynomials of degree $≤2n$ can be represented
as $U↓1(x)x↑n + U↓0(x)$ where deg$(U↓1)$ and deg$(U↓0) ≤ n$;
and $\biglp U↓1(x)x↑n + U↓0(x)\bigrp\biglp V↓1(x)x↑n
+ V↓0(x)\bigrp = U↓1(x)V↓1(x)(x↑{2n} + x↑n) + \biglp U↓1(x)
+ U↓0(x)\bigrp\biglp V↓1(x) + V↓0(x)\bigrp x↑n + U↓0(x)V↓0(x)(x↑n
+ 1)$.\xskip (This equation assumes that arithmetic is being done
modulo 2.)\xskip Thus Eqs.\ 4.3.3--3, 4, 5 hold.

{\sl Notes:} S. A. Cook has shown that Algorithm
4.3.3C can be extended in a similar way, and exercise 4.6.4--14
describes a method requiring even fewer operations for large
$n$. But these ideas are not useful for ``sparse'' polynomials
(having mostly zero coefficients).

%folio 796 galley 11c (C) Addison-Wesley 1978	*
\def\\#1({\mathop{\hjust{#1}}(}\def\+#1\biglp{\mathop{\hjust{#1}}\biglp}
\ansbegin{4.6.1}

\ansno 1. $q(x) = 1 \cdot 2↑3x↑3 + 0
\cdot 2↑2x↑2 - 2 \cdot 2x + 8 = 8x↑3 - 4x + 8$;\xskip$r(x) = 28x↑2
+ 4x + 8$.

\ansno 2. The monic sequence of polynomials produced
during Euclid's algorithm has the coefficients $(1, 5, 6, 6,
1, 6, 3)$, $(1, 2, 5, 2, 2, 4, 5)$, $(1, 5, 6, 2, 3, 4)$, $(1, 3,
4, 6)$, 0. Hence the greatest common divisor is $x↑3 + 3x↑2 +
4x + 6$.\xskip (The greatest common divisor of a polynomial and its
reverse is always symmetric, in the sense that it is a unit
multiple of its own reverse.)

\ansno 3. The procedure of Algorithm 4.5.2X is
valid, with polynomials over $S$ substituted for integers. When
the algorithm terminates, we have $U(x) = u↓2(x)$, $V(x) = u↓1(x)$.
Let $m =\\deg(u)$, $n =\\deg(v)$. It is easy to prove by induction
that $\\deg(u↓3) +\\deg(v↓1) = n$, $\\deg(u↓3) +\\deg(v↓2) = m$,
after step X3, throughout the execution of the algorithm, provided
that $m ≥ n$. Hence if $m$ and $n$ are greater than $d =\+deg\biglp
\gcd(u, v)\bigrp$ we have $\\deg(U) < m - d$, $\\deg(V) < n - d$;
the exact degrees are $m - d↓1$ and $n - d↓1$, where $d↓1$ is
the degree of the second-last nonzero remainder. If $d = \min(m,
n)$, say $d = n$, we have $U(x) = 0$ and $V(x) = 1$.

When $u(x) = x↑m - 1$ and $v(x) = x↑n - 1$, the
identity $(x↑m - 1)\mod(x↑n - 1) = x↑{m\mod n} - 1$ shows that
all polynomials occurring during the calculation are monic, with
integer coefficients. When $u(x) = x↑{21} - 1$ and $v(x) = x↑{13}
- 1$, we have $V(x) = x↑{11} + x↑8 + x↑6 + x↑3 + 1$ and $U(x) =
-(x↑{19} + x↑{16} + x↑{14} + x↑{11} + x↑8 + x↑6 + x↑3 + x)$.\xskip
$\biglp$See also Eq.\ 3.3.3--29, which gives an alternative formula
for $U(x)$ and $V(x)$.$\bigrp$

\ansno 4. Since the quotient $q(x)$ depends only on $v(x)$
and the first $m - n$ coefficients of $u(x)$, the remainder
$r(x) = u(x) - q(x)v(x)$ is uniformly distributed and independent
of $v(x)$. Hence each step of the algorithm may be regarded
as independent of the others; this algorithm is much more well-behaved
than Euclid's algorithm over the integers.

The probability that $n↓1 = n - k$ is $p↑{1-k}(1
- 1/p)$, and $t = 0$ with probability $p↑{-n}$. Each succeeding
step has essentially the same behavior; hence we can see that
any given sequence of degrees $n$, $n↓1$, $\ldotss$, $n↓t$, $-∞$ occurs
with probability $(p - 1)↑t/p↑n$. To find the average value
of $f(n↓1, \ldotss , n↓t)$, let $S↓t$ be the sum of $f(n↓1, \ldotss
, n↓t)$ over all sequences $n > n↓1 >\cdots > n↓t
≥ 0$ having a given value of $t$; then the average is $\sum
↓t S↓t(p - 1)↑t/p↑n$.

Let $f(n↓1, \ldotss , n↓t) = t$; then
$S↓t = {n\choose t}(t + 1)$, so the average is $n(1 - 1/p)$. Similarly,
if $f(n↓1, \ldotss , n↓t) = n↓1 +\cdots + n↓t$, then
$S↓t = {n\choose2}{n-1\choose t-1}$, and the average is ${n\choose2}(1
- 1/p)$. Finally, if $f(n↓1, \ldotss , n↓t) = (n - n↓1)n↓1 +\cdots
+ (n↓{t-1} - n↓t)n↓t$, then $S↓t = {{n+2\choose t+2}
- (n + 1){n+1\choose t+1}}+ {n+1\choose2}{n\choose t}$, and the
average is ${{n+1\choose2} - (n + 1)p/(p - 1)} + {\biglp p/(p -
1)\bigrp ↑2(1 - 1/p↑{n+1})}$.

As a consequence we can see that if $p$ is large
there is very high probability that $n↓{j+1} = n↓j - 1$ for
all $j$.\xskip (If this condition fails over the rational numbers,
it fails for all $p$, so we have further evidence for the text's
claim that Algorithm C almost always finds $\delta↓2 =\cdots
= 1$.)

\ansno 5. Using the formulas developed
in exercise 4, with $f(n↓1, \ldotss , n↓t) = \delta ↓{n↓t0}$,
we find that the probability is $1 - 1/p$ if $n > 0$, 1 if
$n = 0$.

\ansno 6. Assuming that the constant terms $u(0)$
and $v(0)$ are nonzero, imagine a ``right-to-left'' division
algorithm, $u(x) = v(x)q(x) + x↑{m-n}r(x)$, where $\\deg(r) <\\deg(v)$.
We obtain a gcd algorithm anlogous to Algorithm 4.5.2B\null, which
is essentially Euclid's algorithm applied to the ``reverse''
of the original inputs (cf.\ exercise 2), afterwards reversing
the answer and multiplying by an appropriate power of $x$.

\ansno 7. The units of $S$ (as polynomials of degree
zero).
%folio 797 galley 12 (C) Addison-Wesley 1978	*
\def\\#1({\mathop{\hjust{#1}}(}\def\+#1\biglp{\mathop{\hjust{#1}}\biglp}
\ansno 8. If $u(x) = v(x)w(x)$, where $u(x)$ has
integer coefficients while $v(x)$ and $w(x)$ have rational coefficients,
there are integers $m$ and $n$ such that $m\cdot v(x)$ and $n \cdot
w(x)$ have integer coefficients. Now $u(x)$ is primitive, so
we have
$$u(x) = \pm\,\+pp\biglp m \cdot v(x)\bigrp\+pp\biglp n \cdot w(x)\bigrp.$$

\ansno 9. We can extend Algorithm E as follows:
Let $\biglp u↓1(x), u↓2(x), u↓3, u↓4(x)\bigrp$ and $\biglp v↓1(x),
v↓2(x)$, $v↓3, v↓4(x)\bigrp$ be quadruples that satisfy the relations
$u↓1(x)u(x) + u↓2(x)v(x) = u↓3u↓4(x)$, \ $v↓1(x)u(x) + v↓2(x)v(x)
= v↓3v↓4(x)$. The extended algorithm starts with the quadruples $\biglp 1, 0,
\\cont(u), \\pp(u(x))\bigrp$ and $\biglp 0, 1, \\cont(v), \\pp(v(x))\bigrp$
and manipulates them in such a way as to preserve
the above conditions, where $u↓4(x)$ and $v↓4(x)$ run through the
same sequence as $u(x)$ and $v(x)$ do in Algorithm E\null. If $au↓4(x)
= q(x)v↓4(x) + br(x)$, we have $av↓3\biglp u↓1(x), u↓2(x)\bigrp
- q(x)u↓3\biglp v↓1(x), v↓2(x)\bigrp = \biglp r↓1(x), r↓2(x)\bigrp
$, where $r↓1(x)u(x) + r↓2(x)v(x) = bu↓3v↓3r(x)$, so the extended
algorithm can preserve the desired relations. If $u(x)$ and
$v(x)$ are relatively prime, the extended algorithm eventually
finds $r(x)$ of degree zero, and we obtain $U(x) = r↓2(x)$, $V(x)
= r↓1(x)$ as desired.\xskip$\biglp$In practice we would divide $r↓1(x)$,
$r↓2(x)$, and $bu↓3v↓3$ by $\gcd\biglp\\cont(r↓1),\\ cont(r↓2)\bigrp$.$\bigrp
$\xskip Conversely, if such $U(x)$ and $V(x)$ exist, then $u(x)$ and
$v(x)$ have no common prime divisors, since they are primitive
and have no common divisors of positive degree.

\ansno 10. By successively factoring polynomials
that are reducible into polynomials of smaller degree, we must
obtain a finite factorization of any polynomial into irreducibles.
The factorization of the {\sl content} is unique. To show that
there is at most one factorization of the primitive part, the
key result is to prove that if $u(x)$ is an irreducible factor
of $v(x)w(x)$, but not a unit multiple of the irreducible polynomial
$v(x)$, then $u(x)$ is a factor of $w(x)$. This can be proved
by observing that $u(x)$ is a factor of $v(x)w(x)U(x) = rw(x)
- w(x)u(x)V(x)$ by the result of exercise 9, where $r$ is a
nonzero constant.

\ansno 11. The only row names needed
would be $A↓1$, $A↓0$, $B↓4$,
$B↓3$, $B↓2$, $B↓1$, $B↓0$, $C↓1$, $C↓0$, $D↓0$. In general, let $u↓{j+2}(x)
= 0$; then the rows needed for the proof are $A↓{n↓2-n↓j}$
through $A↓0$, $B↓{n↓1-n↓j}$ through $B↓0$, $C↓{n↓2-n↓j}$ through $C↓0$, 
$D↓{n↓3-n↓j}$ through $D↓0$, etc.

\ansno 12. If $n↓k = 0$, the text's proof of (24) shows that the value of
the determinant is $\pm h↓k$, and this equals $\pm\lscr↓k↑{n↓{k-1}}/
\prod↓{1<j<k}\lscr↓{\!j}↑{\delta↓{j-1}(\delta↓j-1)}$.
If the polynomials have a factor
of positive degree, we can artificially assume that the polynomial
zero has degree zero and use the same formula with $\lscr↓k=
0$.

{\sl Notes:} The value $R(u, v)$ of Sylvester's determinant
is called the {\sl resultant} of $u$ and $v$, and the quantity
$(-1)↑{\hjust{\:e deg}(u)(\hjust{\:e deg}(u)-1)/2}\lscr(u)↑{-1}R(u, u↑\prime )$ is
called the {\sl discriminant} of $u$, where $u↑\prime$ is the derivative of $u$. 
If $u(x) = a(x - α↓1)
\ldotsm (x - α↓m)$ and $v(x) = b(x - β↓1) \ldotsm (x - β↓n)$,
we have $R(u, v) = a↑nv(α↓1) \ldotsm v(α↓m) = (-1)↑{mn}b↑mu(β↓1)
\ldotsm u(β↓n) = a↑nb↑m \prod↓{1≤i≤m,1≤j≤n}(α↓i - β↓j)$. It follows
that the polynomials of degree $mn$ in $y$ defined as the respective
resultants with $v(x)$ of $u(y - x)$, $u(y + x)$, $x↑mu(y/x)$, and $u(yx)$
have as respective roots the sums $α↓i + β↓j$, differences
$α↓i - β↓j$, products $α↓iβ↓j$, and quotients $α↓i/β↓j$ $\biglp$when
$v(0) ≠ 0\bigrp $. This idea has been used by R. G. K.
Loos to construct algorithms for arithmetic on algebraic numbers
[{\sl SIAM J. Computing} ({\sl c}. 1979), to appear].

If we replace each row $A↓i$ in Sylvester's matrix by
$$(b↓0A↓i + b↓1A↓{i+1} +\cdots + b↓{n↓2-1-i}A↓{n↓2-1})
- (a↓0B↓i + a↓1B↓{i+1} + \cdots + a↓{n↓2-1-i}B↓{n↓2-1}),$$
and then delete rows $B↓{n↓2-1}$
through $B↓0$ and the last $n↓2$ columns, we obtain an $n↓1
\times n↓1$ determinant for the resultant instead of the original
$(n↓1 + n↓2) \times (n↓1 + n↓2)$ determinant. In some cases
the resultant can be evaluated efficiently by means of this
determinant; see {\sl CACM \bf 12} (1969), 23--30, 302--303.

J. T. Schwartz has shown that resultants and Sturm sequences for
polynomials of degree $n$ can be evaluated with $O\biglp n(\log n)↑2\bigrp$
operations as $n→∞$.\xskip [``Probabilistic algorithms for verification of
polynomial identities,'' to appear.]

\ansno 13. One can show by induction on $j$ that the values of $\biglp
u↓{j+1}(x),g↓{j+1},h↓j\bigrp$ are replaced respectively by $\biglp\lscr↑{1+p↓{j\,}}
w(x)u↓j(x),\lscr↑{2+p↓{j\,}}g↓j,\lscr↑{p↓{j\,}}h↓j\bigrp$ for $j≥2$, 
where $p↓j=n↓1+n↓2-2n↓j$.\xskip
$\biglp$In spite of this growth, the bound (26) remains valid.$\bigrp$

\ansno 14. Let $p$ be a prime of the domain, and let $j,k$ be
maximum such that $p↑k\rslash v↓n = \lscr(v)$, $p↑j\rslash v↓{n-1}$.
Let $P = p↑k$. By Algorithm R we may write $q(x) = a↓0 + Pa↓1x
+\cdots + P↑sa↓sx↑s$, where $s = m - n ≥ 2$. Let
us look at the coefficients of $x↑{n+1}$, $x↑n$, and $x↑{n-1}$
in $v(x)q(x)$, namely $Pa↓1v↓n + P↑2a↓2v↓{n-1} +\cdotss$, $a↓0v↓n
+ Pa↓1v↓{n-1} +\cdotss$, and $a↓0v↓{n-1} + Pa↓1v↓{n-2} +\cdotss$,
each of which is a multiple of $P↑3$. We conclude from the first
that $p↑j\rslash a↓1$, from the second that $p↑{\min(k,2j)}\rslash
a↓0$, then from the third that $P\rslash a↓0$. Hence $P\rslash
r(x)$.\xskip $\biglp$If $m$ were only $n + 1$, the best we could prove would
be that $p↑{\lceil k/2\rceil }$ divides $r(x)$; e.g., consider
$u(x) = x↑3 + 1$, $v(x) = 4x↑2 + 2x + 1$, $r(x) = 18$. On the other hand, an
argument based on determinants of matrices like (21) and (22) can be used to
show that \def\\{\hjust{\:e deg}}$\lscr(r)↑{\\(v)-\\(r)-1}r(x)$ is always a
multiple of $\lscr(v)↑{(\\(u)-\\(v))(\\(v)-\\(r)-1)}$.$\bigrp$
%folio 800 galley 13 (C) Addison-Wesley 1978	*
\def\\#1({\mathop{\hjust{#1}}(}\def\+#1\biglp{\mathop{\hjust{#1}}\biglp}
\ansno 15. Let $c↓{ij} = a↓{i1}a↓{j1} +\cdots +
a↓{in}a↓{jn}$; we may assume that $c↓{ii} > 0$ for all $i$.
If $c↓{ij} ≠ 0$ for some $i ≠ j$, we can replace row $i$ by
$(a↓{i1} - ca↓{j1}, \ldotss , a↓{in} - ca↓{jn})$, where $c =
c↓{ij}/c↓{jj}$; this does not change the value of the determinant,
and it decreases the value of the upper bound we wish to prove,
since $c↓{ii}$ is replaced by $c↓{ii} - c↑{2}↓{ij}/c↓{ij}$.
These replacements can be done in a systematic way for increasing
$i$ and for $j < i$, until $c↓{ij} = 0$ for all $i ≠ j$.\xskip $\biglp$The
latter algorithm is called ``Schmidt's orthogonalization process'';
see {\sl Math.\ Annalen \bf 63} (1907), 442.$\bigrp$ Then $\det(A)↑2
= \det(AA↑T) = c↓{11} \ldotsm c↓{nn}$.

\ansno 16. Let $f(x↓1, \ldotss , x↓n) =
g↓m(x↓2, \ldotss , x↓n)x↑{m}↓{1} +\cdots + g↓0(x↓2,
\ldotss , x↓n)$, and let $g(x↓2, \ldotss , x↓n) = g↓m(x↓2, \ldotss
, x↓n)↑2 +\cdots + g↓0(x↓2, \ldotss , x↓n)↑2$; the
latter is not identically zero. We have $a↓N ≤ m(2N + 1)↑{n-1}
+ (2N + 1)b↓N$, where $b↓N$ counts the integer solutions
of $g(x↓2, \ldotss , x↓n) = 0$ with variables bounded by $N$.
Hence $\lim↓{N→∞} a↓N/(2N + 1)↑n = \lim↓{N→∞} b↓N/(2N + 1)↑{n-1}$,
and this is zero by induction.

\ansno 17. (a) For convenience, let us describe the algorithm
only for $A = \{a, b\}$. The hypotheses imply that $\\deg(Q↓1U)
=\\deg(Q↓2V) ≥ 0$, and $\\deg(Q↓1) ≤\\deg(Q↓2)$. If $\\deg(Q↓1)
= 0$, then $Q↓1$ is just a nonzero rational number, so we set
$Q = Q↓2/Q↓1$. Otherwise we let $Q↓1 = aQ↓{11} + bQ↓{12} + r↓1$,
$Q↓2 = aQ↓{21} + bQ↓{22} + r↓2$, where $r↓1$ and $r↓2$ are rational
numbers; it follows that
$$Q↓1U - Q↓2V = a(Q↓{11}U - Q↓{21}V) + b(Q↓{12}U - Q↓{22}V)
+ r↓1U - r↓2V.$$
We must have either $\\deg(Q↓{11}) =\\deg(Q↓1) -
1$ or $\\deg(Q↓{12}) =\\deg(Q↓1) - 1$. In the former case, $\\deg(Q↓{11}U
- Q↓{21}V) <\\deg(Q↓{11}U)$, by considering the terms of highest
degree that start with $a$; so we may replace $(Q↓1, Q↓2)$
by $(Q↓{12}, Q↓{22})$ and repeat the process.

(b) We may assume that $\\deg(U) ≥\\deg(V)$. If
$\\deg(R) ≥\\deg(V)$, note that $Q↓1U - Q↓2V = Q↓1R - {(Q↓2 -
Q↓1Q)}V$ has degree less than $\\deg(V) ≤\\deg(Q↓1R)$, so we can
repeat the process with $U$ replaced by $R$; we obtain $R =
Q↑\prime V + R↑\prime$, $U = (Q + Q↑\prime )V + R↑\prime $, where
$\\deg(R↑\prime ) <\\deg(R)$, so eventually a solution will be
obtained.

(c) The algorithm of (b) gives $V↓1 = UV↓2 + R$,
$\\deg(R) <\\deg(V↓2)$; by homogeneity, $R = 0$ and $U$ is homogeneous.

(d) We may assume that $\\deg(V) ≤\\deg(U)$. If
$\\deg(V) = 0$, set $W ← U$; otherwise use (c) to find $U = QV$,
so that $QVV = VQV$, $(QV - VQ)V = 0$. This implies that $QV =
VQ$, so we can set $U ← V$, $V ← Q$ and repeat the process.

For further details about the subject of this
exercise, see P. M. Cohn, {\sl Proc.\ Cambridge Phil.\ Soc.\ \bf 57}
(1961), 18--30. The considerably more difficult problem of characterizing
{\sl all} string polynomials such that $UV = VU$ has been solved
by G. M. Bergman [Ph.D. thesis, Harvard University, 1967].

\ansno 18. [P. M. Cohn, {\sl Transactions Amer.\ Math.\ Soc.\ \bf 109}
(1963), 332--356.]

\yskip\hang\textindent{\bf C1.} Set $u↓1 ← U↓1$, $u↓2
← U↓2$, $v↓1 ← V↓1$, $v↓2 ← V↓2$, $z↓1 ← z↑\prime↓{2} ← w↓1 ← w↑\prime↓{2}
← 1$, $z↑\prime↓{1} ← z↓2 ← w↑\prime↓{1} ← w↓2 ← 0$, $n
← 0$.

\yskip\hang\textindent{\bf C2.} (At this point the identities
given in the exercise hold, and also $u↓1v↓1 = u↓1v↓2$; $v↓2 =
0$ if and only if $u↓1 = 0$.)\xskip If $v↓2 = 0$, the algorithm terminates
with gcrd$(V↓1, V↓2) = v↓1$, lclm$(V↓1, V↓2) = z↑\prime↓{1}V↓1
= -z↑\prime↓{2}V↓2$.\xskip (Also, by symmetry, gcld$(U↓1, U↓2) =
\\lclm(U↓1, U↓2) = U↓1w↓1 = -U↓2w↓2$.)

\yskip\hang\textindent{\bf C3.} Find $Q$ and $R$ such that $v↓1
= Qv↓2 + R$, where $\\deg(R) <\\deg(v↓2)$.\xskip$\biglp$We have $u↓1(Qv↓2
+ R) = u↓2v↓2$, so $u↓1R = (u↓2 - u↓1Q)v↓2 = R↑\prime v↓2.\bigrp$

\yskip\hang\textindent{\bf C4.} Set $(w↓1$, $w↓2$, $w↑\prime↓{1}$,
$w↑\prime↓{2}$, $z↓1$, $z↓2$, $z↑\prime↓{1}$, $z↑\prime↓{2}$,
$u↓1$, $u↓2$, $v↓1$, $v↓2) ← (w↑\prime↓{1} - w↓1Q$, $w↑\prime↓{2}
- w↓2Q$, $w↓1$, $w↓2$, $z↑\prime↓{1}$, $z↑\prime↓{2}$, $z↓1 - Qz↑\prime↓{1}$,
$z↓2 - Qz↑\prime↓{2}$, $u↓2 - u↓1Q$, $u↓1$, $v↓2$, $v↓1 - Qv↓2)$ and
$n ← n + 1$. Go back to C2.\quad\blackslug
%folio 802 galley 1a (C) Addison-Wesley 1978	*
\def\\#1({\mathop{\hjust{#1}}(}\def\+#1\biglp{\mathop{\hjust{#1}}\biglp}
\yyskip This extension of Euclid's algorithm includes most
of the features we have seen in previous extensions, all at
the same time, so it provides new insight into the special cases
already considered. To prove that it is valid, note first that
deg$(v↓2)$ decreases in step C4, so the algorithm certainly
terminates. At the conclusion of the algorithm, $v↓1$ is a common
right divisor of $V↓1$ and $V↓2$, since $w↓1v↓1 = (-1)↑nV↓1$
and $-w↓2v↓1 = (-1)↑nV↓2$; also if $d$ is any common right divisor
of $V↓1$ and $V↓2$, it is a right divisor of $z↓1V↓1 + z↓2V↓2
= v↓1$. Hence $v↓1 =\\gcrd(V↓1, V↓2)$. Also if $m$ is any common
left multiple of $V↓1$ and $V↓2$, we may assume without loss
of generality that $m = U↓1V↓1 = U↓2V↓2$, since the sequence
of values of $Q$ does not depend on $U↓1$ and $U↓2$. Hence $m
= (-1)↑n(-u↓2z↑\prime↓{1})V↓1 = (-1)↑n(u↓2z↑\prime↓{2})V↓2$
is a multiple of $z↑\prime↓{1}V↓1$.

In practice, if we just want to calculate gcrd$(V↓1,
V↓2)$, we may suppress the computation of $n$, $w↓1$, $w↓2$, $w↑\prime↓{1}$,
$w↑\prime↓{2}$, $z↓1$, $z↓2$, $z↑\prime↓{1}$, $z↑\prime↓{2}$.
These additional quantities were added to the algorithm primarily
to make its validity more readily established.

{\sl Note:} Nontrivial factorizations of string
polynomials, such as the example given with this exercise, can
be found from matrix identities such as
$$\left({a \atop 1}\qquad{1\atop 0}\right)\left({b\atop 1}\qquad{1\atop
0}\right)\left({c\atop 1}\qquad{1\atop0}\right)\left({0\atop 1}\quad
{\quad1\atop -c}\right)\left({0\atop 1}\quad{\quad1\atop -b}\right)\left({0\atop
1}\quad{\quad1\atop -a}\right) = \left({1\qquad 0\atop 0\qquad 1}\right),$$
since this identities hold even when multiplication is not commutative.
For example,
$$(abc + a + c)(1 + ba) = (ab + 1)(cba + a + c).$$
(Compare this with the ``continuant polynomials'' of Section 4.5.3.)

\ansno 19. (Solution by Michael Fredman.)\xskip If such an algorithm
exists, $D$ is a gcrd by the argument in exercise 18. Let us
regard $A$ and $B$ as a single $2n \times n$ matrix $C$ whose
first $n$ rows are those of $A$, and whose second $n$ rows are
those of $B$. Similarly, $P$ and $Q$ can be combined into a
$2n \times n$ matrix $R$; $X$ and $Y$ can be combined into an
$n \times 2n$ matrix $Z$. The desired conditions now reduce
to two equations $C = RD$, $D = ZC$. If we can find a $2n \times
2n$ integer matrix $U$ of determinant $\pm 1$ such that the last
$n$ rows of $U↑{-1}C$ are all zero, then $R = ($first $n$ columns
of $U)$, $D = ($first $n$ rows of $U↑{-1}C)$, $Z = ($first $n$ rows
of $U↑{-1})$ solves the desired conditions. Hence, for example,
the following algorithm may be used (with $m=2n$):

\algbegin Algorithm T (Triangulation). Let $C$ be an $m \times n$ matrix
of integers. This algorithm finds $m \times m$ integer matrices
$U$ and $V$ such that $UV = I$ and $VC$ is ``upper triangular.''\xskip
(The entry in row $i$ and column $j$ of $VC$ is zero if $i >
j$.)

\algstep T1. [Initialize.] Set $U ← V ← I$, the
$m \times m$ identity matrix; and set $T ← C$.\xskip (Throughout the
algorithm we will have $T = VC$ and $UV = 1$.)

\algstep T2. [Iterate on $j$.] Do step T3 for $j = 1$, 2, $\ldotss
$, $\min(m, n)$, and terminate the algorithm.

\algstep T3. [Zero out column $j$.] Perform the following transformation
zero or more times until $T↓{ij}$ is zero for all $i > j$: Let
$T↓{kj}$ be a nonzero element of $\{T↓{ij}, T↓{(j+1)j}, \ldotss,
T↓{mj}\}$ having the smallest absolute value. Interchange
rows $k$ and $j$ of $T$ and of $V$; interchange columns $k$
and $j$ of $U$. Then subtract $\lfloor T↓{ij}/T↓{jj}\rfloor$
times row $j$ from row $i$, in matrices $T$ and $V$, and add
the same multiple of column $i$ to column $j$ in matrix $U$,
for $j < i ≤ m$.\quad\blackslug

\noindent For the stated example, the
algorithm yields \def\\#1#2#3#4{({#1\atop#3}\;{#2\atop#4})}
$\\1234=\\1032\\1{\quad2}0{-1}$, $\\4321=\\4523\\1{\quad2}0{-1}$,
$\\1{\quad2}0{-1}=\\1{\quad0}2{-2}\\1234
+\\0010\\4321$.\xskip (Actually
{\sl any} matrix with determinant $\pm 1$ would be a gcrd in this particular case.)

\ansno 20. It may be helpful to consider exercise 4.6.2--22
with $p↑m$ replaced by a small number $ε$.

\ansno 21. Note that Algorithm R is used only when $m - n ≤
1$; furthermore, the coefficients are bounded by (25) with $m =
n$.\xskip [The stated formula is, in fact, the execution time observed
in practice, not merely an upper bound. For more detailed information
see G. E. Collins, {\sl Proc. 1968 Summer Inst.\ on Symbolic
Math.\ Comp.}, Robert G. Tobey, ed.\ (IBM Federal Systems Center,
June 1969), 195--231.]

\ansno 22. A sequence of signs cannot contain two consecutive
zeros, since $u↓{k+1}(x)$ is a nonzero constant in (28). Moreover
we cannot have ``+, 0, +'' or ``$-$, 0, $-$'' as subsequences. The formula
$V(u, a) - V(u, b)$ is clearly valid when $b = a$, so we must
only verify it as $b$ increases. The polynomials $u↓j(x)$ have
finitely many roots, and $V(u, b)$ changes only when $b$ encounters
or passes such roots. Let $x$ be a root of some (possibly several)
$u↓j$. When $b$ increases from $x - ε$ to $x$, the sign sequence
near $j$ goes from ``+, $\pm$, $-$'' to ``+, 0, $-$'' or from ``$-$, $\pm$, +''
to ``$-$, 0, +'' if $j > 0$; and from ``+, $-$'' to ``0, $-$'' or from ``$-$, +'' to
``0, +'' if $j = 0$.\xskip (Since $u↑\prime (x)$ is the derivative, $u↑\prime
(x)$ is negative when $u(x)$ is decreasing.)\xskip Thus the net change
in $V$ is $-\delta ↓{j0}$. When $b$ increases from $x$ to $x
+ ε$, a similar argument shows that $V$ remains unchanged.

[L. E. Heindel, {\sl JACM} {\bf 18} (1971), 533--548,
has applied these ideas to construct algorithms for isolating
the real zeroes of a given polynomial $u(x)$, in time bounded
by a polynomial in deg$(u)$ and log $N$, where all coefficients
$y↓j$ are integers with $|u↓j| ≤ N$, and all operations are
guaranteed to be exact.]

\ansno 23. If $v$ has $n - 1$ real roots occurring between the
$n$ real roots of $u$, then (by considering sign changes) $u(x)\mod
v(x)$ has $n - 2$ real roots lying between the $n - 1$ of $v$.

\ansno 24. First show that $h↓j=g↓{\!j}↑{\delta↓{j-1}}g↓{\!j-1}↑{\delta↓{j-2}
(1-\delta↓{j-1})}\ldotss g↓2↑{\delta↓1(1-\delta↓2)\ldotsm(1-\delta↓{j-1})}$.
Then show that the exponent of $g↓2$ on the left-hand side of (18) has the form
$\delta↓2+\delta↓1x$, where $x=\delta↓2+\cdots+\delta↓{j-1}+1-\delta↓2(\delta↓3+
\cdots+\delta↓{j-1}+1)-\delta↓3(1-\delta↓2)(\delta↓4+\cdots+\delta↓{j-1}+1)-\cdots
-{\delta↓{j-1}(1-\delta↓2)\ldotsm(1-\delta↓{j-2})(1)}$. But $x=1$, since
it is seen to be independent of $\delta↓{j-1}$ and we can set $\delta↓{j-1}=0$,
etc. A similar derivation works for $g↓3$, $g↓4$, $\ldotss$, and a simpler
derivation works for (23).

\ansno 25. Each coefficient of $u↓j(x)$ can be expressed as a determinant in
which one column contains only $\lscr(u)$, $\lscr(v)$, and zeros. To use
this fact, modify Algorithm C as follows: In step C1, set $g←\gcd\biglp\lscr(u),
\lscr(v)\bigrp$ and $h←0$.
In step C3, if $h=0$, set $u(x)←v(x)$, $v(x)←r(x)/g$, $h←\lscr(u)↑\delta/g$,
$g←\lscr(u)$, and return to C2; otherwise proceed as in the unmodified
algorithm. The effect of this new initialization is simply to replace
$u↓j(x)$ by $u↓j(x)/\!\gcd\biglp\lscr(u),\lscr(v)\bigrp$ for all $j≥3$;
thus, $\lscr↑{2j-4}$ will become $\lscr↑{2j-5}$ in (27).
%folio 804 galley 1b (C) Addison-Wesley 1978	*
\ansbegin{4.6.2}

\ansno 1. By the principle of inclusion
and exclusion (Section 1.3.3), the number of polynomials without
linear factors is $\sum ↓{k≤n} {p\choose k}p↑{n-k}(-1)↑k = p↑{n-p}(p
- 1)↑p$. The stated probability is therefore $1 - (1 - 1/p)↑p$,
which is greater than ${1\over 2}$.\xskip [In fact, the stated probability
is greater than ${1\over 2}$ for all $n ≥ 1$.]

\ansno 2. (a) We know that $u(x)$ has a representation
as a product of irreducible polynomials; and the leading coefficients
of these polynomials must be units, since they divide the leading
coefficient of $u(x)$. Therefore we may assume that $u(x)$ has
a representation as a product of monic irreducible polynomials
$p↓1(x)↑{e↓1}\ldotsm p↓r(x)↑{e↓r}$, where $p↓1(x)$,
$\ldotss$, $p↓r(x)$ are distinct. This representation is unique,
except for the order of the factors, so the conditions on $u(x)$,
$v(x)$, $w(x)$ are satisfied if and only if
$$v(x) = p↓1(x)↑{\lfloor e↓1/2\rfloor} \ldotss p↓r(x)↑{\lfloor e↓r/2\rfloor},
\qquad w(x) = p↓1(x)↑{e↓1\mod2} \ldotss p↓r(x)↑{e↓r\mod2}.$$

(b) The generating function for the number
of monic polynomials of degree $n$ is $1 + pz + p↑2z↑2 + \cdots
= 1/(1 - pz)$. The generating function for the number of polynomials
of degree $n$ having the form $v(x)↑2$, where $v(x)$ is monic,
is $1 + pz↑2 + p↑2z↑4 + \cdots = 1/(1 - pz↑2)$. If the generating
function for the number of monic squarefree polynomials of degree
$n$ is $g(z)$, then by part (a)  we must have $1/(1 - pz) = g(z)/(1 - pz↑2)$.
Hence $g(z) = (1 - pz↑2)/(1 - pz) = 1 + pz + (p↑2 - p)z↑2 +
(p↑3 - p↑2)z↑3 + \cdotss$. The answer is $p↑n - p↑{n-1}$ for
$n ≥ 2$.\xskip $\biglp$Curiously, this proves that $\gcd\biglp u(x), u↑\prime
(x)\bigrp = 1$ with probability $1 - 1/p$; it is the same as
the probability that $\gcd\biglp u(x), v(x)\bigrp = 1$ when $u(x)$
and $v(x)$ are {\sl independent}, by exercise 4.6.1--5.$\bigrp$

\ansno 3. Let $u(x) = u↓1(x) \ldotsm u↓r(x)$. There is {\sl at
most} one such $v(x)$, by the argument of Theorem 4.3.2C\null. There
is {\sl at least} one if, for each $j$, we can solve the system
with $w↓j(x) = 1$ and $w↓k(x) = 0$ for $k ≠ j$. A solution to
the latter is $v↓1(x)\prod↓{k≠j}u↓k(x)$, where $v↓1(x)$
and $v↓2(x)$ can be found satisfying
$$\textstyle v↓1(x)\prod↓{k≠j}u↓k(x)\,+\,v↓2(x)u↓j(x) = 1,\qquad
\hjust{deg}(v↓1) <\hjust{deg}(u↓j),$$
by the extension of Euclid's algorithm (exercise 4.6.1--3).
%folio 805 galley 2 (C) Addison-Wesley 1978	*
\ansno 4. The unique factorization theorem gives the identity
$(1 - pz)↑{-1} =\prod↓{n≥1} (1 - z↑n)↑{-a↓{np}}$;
after taking logarithms, this can be rewritten$$\textstyle\sum ↓{j≥1} G↓p(z↑j)/j
= \sum ↓{k,j≥1} a↓{kp}z↑{kj}/j = \ln\biglp 1/(1 - pz)\bigrp.$$
The stated identity now yields the answer $G↓p(z) = \sum ↓{m≥1}
\mu (m)m↑{-1}\ln\biglp 1/(1 - pz↑m)\bigrp $, from which we
obtain $a↓{np} = \sum ↓{d\rslash n} \mu (n/d)n↑{-1}p↑d$; thus $\lim↓{p→∞}
a↓{np}/p↑n = 1/n$. To prove the stated identity, note that $\sum
↓{n,j≥1}\mu (n)g(z↑{nj})n↑{-t}j↑{-t} = \sum ↓{m≥1} g(z↑m)m↑{-t}
\sum ↓{n\rslash m} \mu (n) = g(z)$.

\ansno 5. Let $a↓{npr}$ be the number of monic
polynomials of degree $n$ modulo $p$ having exactly $r$ irreducible
factors. Then $\Gscr↓p(z, w) = \sum ↓{n,r≥0} a↓{npr}z↑nw↑r =
\exp\biglp \sum ↓{k≥1} G↓p(z↑k)w↑k/k\bigrp$, where $G↓p$ is the generating
function in exercise 4; cf.\ Eq.\ 1.2.9--34.
We have $$\baselineskip15pt\eqalign{\textstyle\sum ↓{n≥0} A↓{np}z↑n
= d\Gscr↓p(z/p, w)/d↓{\null}w\,|↓{w=1}⊗=\textstyle
\biglp \sum ↓{k≥1}G↓p(z↑k/p↑k)\bigrp \exp\biglp\ln(1/(1
- z))\bigrp\cr⊗\textstyle=\biglp\sum↓{n≥1}\ln\biglp 1/(1-p↑{1-n}z↑n)\bigrp\varphi
(n)/n\bigrp/(1-z),\cr}$$ hence $A↓{np} = H↓n + 1/2p + O(p↑{-2})$ for
$n ≥ 2$. The average value of $2↑r$ is the coefficient of $z↑n$
in $\Gscr↓p(z/p, 2)$, namely $n + 1 + (n - 1)/p + O(p↑{-2})$.\xskip (The
variance is of order $n↑3$, however: set $w = 4$.)

\ansno 6. For $0 ≤ s < p$, $x - s$ is a factor of
$x↑p - x$ (modulo $p$) by Fermat's theorem. So $x↑p - x$ is
a multiple of $\lcm\biglp x - 0, x - 1, \ldotss , x - (p - 1)\bigrp=x↑{\underline p}
$.\xskip $\biglp${\sl Note:} Therefore the Stirling numbers
$p\comb[]k$ are multiples of $p$ except when $k = 1$, $k =
p$. Equation 1.2.6--41 shows that the same statement is valid
for Stirling numbers $p\comb\{\} k$ of the other kind.$\bigrp$

\ansno 7. The factors on the right are relatively
prime, and each is a divisor of $u(x)$, so their product divides
$u(x)$. On the other hand,
$$\textstyle u(x)\qquad\hjust{divides}\qquad v(x)↑p - v(x) = \prod ↓{0≤s<p}
\biglp v(x) - s\bigrp ,$$
so it divides the right-hand side by exercise 4.5.2--2.

\ansno 8. The vector (18) is the only output whose $k$th component is nonzero.

\ansno 9. For example, start with $x ← 1$, $y ← 1$;
then repeatedly set $R[x] ← y$, $x ←2x \mod 101$, $y ← 51y
\mod 101$, one hundred times.

\ansno 10. The matrix $Q - I$ below has a null space generated
by the two vectors $v↑{[1]} =(1, 0, 0, 0, 0, 0, 0, 0)$, $v↑{[2]}
= (0, 1, 1, 0, 0, 1, 1, 1)$. The factorization is
$$(x↑6 + x↑5 + x↑4 + x + 1)(x↑2 + x + 1).$$

\hjust to size{\qquad$\dispstyle{p=2\lower5pt\null\atop
\left(\,\vcenter{\halign{\hfill#⊗\hjust to 15pt{\hfill#}⊗\!
\hjust to 15pt{\hfill#}⊗\hjust to 15pt{\hfill#}⊗\hjust to 15pt{\hfill#}⊗\!
\hjust to 15pt{\hfill#}⊗\hjust to 15pt{\hfill#}⊗\hjust to 15pt{\hfill#}\cr
0⊗0⊗0⊗0⊗0⊗0⊗0⊗0\cr
0⊗1⊗1⊗0⊗0⊗0⊗0⊗0\cr
0⊗0⊗1⊗0⊗1⊗0⊗0⊗0\cr
0⊗0⊗0⊗1⊗0⊗0⊗1⊗0\cr
1⊗0⊗0⊗1⊗0⊗0⊗1⊗0\cr
1⊗0⊗1⊗1⊗1⊗0⊗0⊗0\cr
0⊗0⊗1⊗0⊗1⊗1⊗0⊗1\cr
1⊗1⊗0⊗1⊗1⊗1⊗0⊗1\cr}}\,\right)}\hfill{p=5\lower5pt\null\atop
\left(\,\vcenter{\halign{\hfill#⊗\hjust to 15pt{\hfill#}⊗\!
\hjust to 15pt{\hfill#}⊗\hjust to 15pt{\hfill#}⊗\!
\hjust to 15pt{\hfill#}⊗\hjust to 15pt{\hfill#}⊗\hjust to 15pt{\hfill#}\cr
0⊗0⊗0⊗0⊗0⊗0⊗0\cr
0⊗4⊗0⊗0⊗0⊗1⊗0\cr
0⊗2⊗2⊗0⊗4⊗3⊗4\cr
0⊗1⊗4⊗4⊗4⊗2⊗1\cr
2⊗2⊗2⊗3⊗4⊗3⊗2\cr
0⊗0⊗4⊗0⊗1⊗3⊗2\cr
3⊗0⊗2⊗1⊗4⊗2⊗1\cr}}\,\right)}$\qquad}

\ansno 11. Removing the trivial factor
$x$, the matrix $Q - I$ above has a null space generated by
$(1, 0, 0, 0, 0, 0, 0)$ and $(0, 3, 1, 4, 1, 2, 1)$. The factorization
is
$$x(x↑2 + 3x + 4)(x↑5 + 2x↑4 + x↑3 + 4x↑2 + x + 3).$$

\ansno 12. If $p = 2$, $(x + 1)↑4 = x↑4 + 1$. If $p
= 8k + 1$, $Q - I$ is the zero matrix, so there are four factors.
For other values of $p$ we have
$$\lower18pt\hjust{$Q-I=\null$}
{p=8k+3\lower5pt\null\atop
\left(\,\vcenter{\halign{\hfill#⊗\hjust to 20pt{\hfill$#$}⊗\!
\hjust to 20pt{\hfill$#$}⊗\hjust to 20pt{\hfill$#$}⊗\hjust to 20pt{\hfill$#$}\cr
0⊗0⊗0⊗0\cr0⊗-1⊗0⊗1\cr0⊗0⊗-2⊗0\cr0⊗1⊗0⊗-1\cr}}\,\right)}
{p=8k+5\lower5pt\null\atop
\left(\,\vcenter{\halign{\hfill#⊗\hjust to 20pt{\hfill$#$}⊗\!
\hjust to 20pt{\hfill$#$}⊗\hjust to 20pt{\hfill$#$}⊗\hjust to 20pt{\hfill$#$}\cr
0⊗0⊗0⊗0\cr0⊗-2⊗0⊗0\cr0⊗0⊗0⊗0\cr0⊗0⊗0⊗-2\cr}}\,\right)}
{p=8k+7\lower5pt\null\atop
\left(\,\vcenter{\halign{\hfill#⊗\hjust to 20pt{\hfill$#$}⊗\!
\hjust to 20pt{\hfill$#$}⊗\hjust to 20pt{\hfill$#$}⊗\hjust to 20pt{\hfill$#$}\cr
0⊗0⊗0⊗0\cr0⊗-1⊗0⊗-1\cr0⊗0⊗-2⊗0\cr0⊗-1⊗0⊗-1\cr}}\,\right)}$$
Here $Q - I$ has rank 2, so there are $4
- 2 = 2$ factors.\xskip $\biglp$But it is easy to prove that $x↑4 + 1$ is
irreducible over the integers, since it has no linear factors
and the coefficient of $x$ in any factor of degree two must
be less than or equal to 2 in absolute value by exercise 20.
For all $k ≥ 2$, H. P. F. Swinnerton-Dyer has exhibited polynomials
of degree $2↑k$ that are irreducible over the integers, but
they split completely into linear and quadratic factors modulo
every prime. For degree 8, his example is $x↑8 - 16x↑6 + 88x↑4
+192x↑2 + 144$, having roots $\pm\sqrt 2\pm\sqrt3\pm i$ [see {\sl Math.\
Comp.\ \bf24} (1970), 733--734]. According to the theorem of Frobenius cited
in exercise 33, any irreducible polynomial of degree $n$
whose Galois group contains no $n$-cycles will have factors modulo almost
all primes.$\bigrp$

\ansno 13. $p=8k+1$:
${\biglp x+(1+\sqrt{-1})/\sqrt2\bigrp}\*
{\biglp x+(1-\sqrt{-1})/\sqrt2\bigrp}\*
{\biglp x-(1+\sqrt{-1})/\sqrt2\bigrp}\*
{\biglp x-(1-\sqrt{-1})/\sqrt2\bigrp}$.\xskip
$p=8k+3$: ${\biglp x↑2-\sqrt{-2}x-1\bigrp}\*
{\biglp x↑2-\sqrt{-2}x-1\bigrp}$.\xskip
$p=8k+5$: ${\biglp x↑2-\sqrt{-1}\bigrp}\*
{\biglp x↑2-\sqrt{-1}\bigrp}$.\xskip
$p=8k+7$: ${\biglp x↑2-\sqrt2x+1\bigrp}\*
{\biglp x↑2+\sqrt2x+1\bigrp}$. The latter factorization also holds over the
field of real numbers.

\ansno 14. The gcd is 1 when $(s↓i+t)↑{(p-1)/2}≡0$ or $-1$ for all $i$;
it is $w(x)$ when $(s↓i+t)↑{(p-1)/2}≡1$ for all $i$. To get a lower bound
on $P$, let $k=2$. The ``bad'' values of $t$ satisfy $t≡-s↓1$ or $t≡-s↓2$
or $\biglp(s↓1+t)/(s↓2+t)\bigrp↑{(p-1)/2}≡1$. Furthermore $(s↓1+t)/(s↓2+t)$
runs through all values except 0 and 1 as $t$ runs through all values other
than $-s↓1$ and $-s↓2$, modulo\penalty999\
$p$. Hence there are at most $2+(p-1)/2-1$
bad values.  $\biglp$If $t≡-s↓1$ and $t≡-s↓2$ are both bad, then $(-1)↑{(p-1)/2}≡1$;
thus $P≥1/2+1/(2p)$ when $p≡3\modulo4$.$\bigrp$

{\sl Notes:} It follows that with probability $>1-ε$ we will find a root of
$w(x)$ modulo $p$ in $O\biglp(\log(1/ε))(\log k)(k↑2(\log p)↑3+k↑3(\log p)↑2)\bigrp$
units of time.\xskip
$\biglp$The factor $\log(1/ε)$ is the number of independent trials
needed per reduction, while $\log k$ is the maximum number of reductions, since the
degree is at worst halved when a nontrivial factorization is found;
$k↑2(\log p)↑3$ units of time will evaluate $(x+t)↑{(p-1)/2}\mod w(x)$, while
$k↑3(\log p)↑2$ suffice to compute the gcd.$\bigrp$\xskip
On the other hand, the true behavior is probably better than these ``worst-case''
estimates. Suppose that each linear factor $x-s↓i$ has probability $1\over2$ of
dividing $(x+t)↑{(p-1)/2}-1$ for each $t$, independent of the behavior for
other $s↓j$ and $t$. Then if we encode each $s↓i$ by a sequence of 0's and 1's
according as $x-s↓i$ does or doesn't divide $(x+t)↑{(p-1)/2}-1$ for the successive
$t$'s tried, we obtain a random binary trie with $k$ lieves (cf.\ Section 6.3).
The cost associated with an internal node of this trie, having $d$ lieves as
descendants, is $O\biglp d↑2(\log p)↑3+d↑3(\log p)↑2\bigrp$. The solution to
the recurrences $A↓n={n\choose2}+2↑{1-n}\sum{n\choose k}A↓k$,
$B↓n={n\choose3}+2↑{1-n}\sum{n\choose k}B↓k$, is $A↓n=2{n\choose2}$,
$B↓n={4\over3}{n\choose3}$, by exercise 5.2.2--36. Hence the sum of costs
in the given random trie---representing the time to factor $w(x)$ {\sl
completely}---is $O\biglp k↑2(\log p)↑3+k↑3(\log p)↑2\bigrp$ under this
plausible assumption.

\ansno 15. We may assume that $u≠0$ and that $p$ is odd. Berlekamp's method applied
to the polynomial $x↑2-u$ tells us that a square root exists if and only if
$u↑{(p-1)/2}\mod p=1$; let us assume that this condition holds.

Let $p-1=2↑e\cdot q$, where $q$ is odd. Zassenhaus's factoring procedure suggests
the following square-root extraction algorithm: Set $t←0$. Evaluate
$$\twoline{\gcd\biglp(x+t)↑q-1,x↑2-u\bigrp,\;\gcd\biglp(x+t)↑{2q}-1,x↑2
-u\bigrp,}{2pt}{\gcd\biglp(x+t)↑{4q}-1,x↑2-u\bigrp,\;\gcd\biglp(x+t)↑{8q}-1,
x↑2-u\bigrp,\;\ldotss,}$$
until finding the first case where the gcd is not 1 (modulo $p$). If the
gcd is $x-v$, then $\sqrt u = \pm v$. If the gcd is $x↑2-u$, set $t←t+1$ and
repeat the calculation.

{\sl Notes:} If $(x+t)↑k\mod(x↑2-u)=ax+b$, then we have $(x+t)↑{k+1}\mod(x↑2-u)=
(b+at)x+(bt+au)$, and $(x+t)↑{2k}\mod(x↑2-u)=2abx+(b↑2+a↑2u)$; hence
$(x+t)↑q$, $(x+t)↑{2q}$, $\ldots$ are easy to evaluate efficiently, and the
calculation for fixed $t$ takes $O\biglp(\log p)↑3\bigrp$ units of time.
The square root will be found when $t=0$ with probability $1/2↑{e-1}$;
thus it will always be found immediately when $p\mod4=3$. If we choose
$t$ at random instead of increasing it sequentially, exercise 14 gives a
rigorous proof that each $t$ gives success at least about half of the time;
but for practical purposes this random choice isn't needed.

Another square-root method has been suggested by D. Shanks. When $e>1$ it
requires an auxiliary constant $z$ (depending only on $p$) such that
$z↑{2↑{e-1}}≡-1\modulo p$. The value $z=n↑q\mod p$ will work for almost
one half of all integers $n$; once $z$ is known, the following algorithm
requires no more probabilistic calculation:

\yskip\hang\textindent{\bf S1.}Set $y←z$, $r←e$, $v←u↑{(q+1)/2}\mod p$,
$w←u↑q\mod p$.

\yskip\hang\textindent{\bf S2.}If $w=1$, stop; $v$ is the answer. Otherwise
find the smallest $k$ such that $w↑{2↑k}\mod p$ is equal to 1.
If $k=r$, stop (there is
no answer); otherwise set$$(y,r,v,w)←(y↑{2↑{r-k}},k,vy↑{2↑{r-k-1}},wy↑{2↑{r-k}})$$
and repeat step S2.\quad\blackslug

\yyskip The validity of this algorithm follows from the invariant congruences
$uw≡v↑2$, $y↑{2↑{r-1}}≡-1$, $w↑{2↑{r-1}}≡1\modulo p$. On the average, step S2
will require about ${1\over4}e↑2$ multiplications mod $p$.\xskip
Reference: {\sl Proc.\ Second Manitoba Conf.\ Numer.\ Math.\ }(1972),
\hjust{58--62.} A related method was published by A. Tonelli, {\sl G\"ottinger
Nachrichten} (1891), 344--346.
%folio 810 galley 3 (C) Addison-Wesley 1978	*
\ansno 16. (a) Substitute polynomials modulo $p$ for integers,
in the proof for $n = 1$.\xskip (b) The proof for $n=1$
carries over to any finite field.\xskip (c) Since $x = \xi ↑k$ for
some $k$, $x↑{p↑n} = x$ in the field defined by $f(x)$. Furthermore, the elements
$y$ that satisfy the equation $y↑{p↑m} = y$ in the field
are closed under addition, and closed under multiplication;
so if $x↑{p↑m}= x$, then $\xi$ (being a polynomial in
$x$ with integer coefficients) satisfies $\xi↑{p↑m} =
\xi $.

\ansno 17. If $\xi$ is a primitive root, each nonzero element
is some power of $\xi $. Hence the order must be a divisor of
$13↑2 - 1 = 2↑3 \cdot 3 \cdot 7$, and $\varphi (f)$ elements have
order $f$.
\def\\#1{\hjust{$\hfill\hskip-10pt#1\hskip-10pt\hfill$}\hfill}
$$\vjust{\halign{\hfill#⊗\qquad\hfill#⊗\qquad\qquad\hfill#⊗\qquad\hfill#⊗\!
\qquad\qquad\hfill#⊗\qquad\hfill#⊗\qquad\qquad\hfill#⊗\qquad\hfill#\cr
\\f⊗\\{\varphi(f)}⊗\\f⊗\\{\varphi(f)}⊗\\f⊗\\{\varphi(f)}⊗\\f⊗\\{\varphi(f)}\cr
\noalign{\vskip3pt}
1⊗1⊗3⊗2⊗7⊗6⊗21⊗12\cr
2⊗1⊗6⊗2⊗14⊗6⊗42⊗12\cr
4⊗2⊗12⊗4⊗28⊗12⊗84⊗24\cr
8⊗4⊗24⊗8⊗56⊗24⊗168⊗48\cr}}$$

\ansno 18. (a) pp$\biglp p↓1(u↓nx)\bigrp \ldotsm\hjust{pp}
\biglp p↓r(u↓nx)\bigrp$, by Gauss's lemma. For example, let
$$u(x) = 6x↑3 - 3x↑2 + 2x - 1,\qquad v(x) = x↑3 - 3x↑2 + 12x
- 36 = (x↑2 + 12)(x - 3);$$
then pp$(36x↑2 + 12) = 3x↑2 + 1$, pp$(6x - 3) =
2x - 1$.\xskip (This is a modern version of a fourteenth-century trick
used for many years to help solve algebraic equations.)

(b) Let pp$\biglp w(u↓nx)\bigrp = \=w↓mx↑m
+ \cdots + \=w↓0 = w(u↓nx)/c$, where $c$ is the content
of $w(u↓nx)$ as a polynomial in $x$. Then $w(x) = (c\=w/u↑{m}↓{n})x↑m
+ \cdots + c\=w↓0$, hence $c\=w↓m = u↑{m}↓{n}$;
since $\=w↓m$ is a divisor of $u↓n$, $c$ is a multiple of $u↑{m-1}↓{n}$.

\ansno 19. If $u(x) = v(x)w(x)$ with deg$(v)$deg$(w) ≥
1$, then $u↓nX↑n ≡ v(x)w(x) \modulo p$. By unique factorization
modulo $p$, all but the leading coefficients of $v$ and $w$ are multiples of $p$,
and $p↑2$ divides $v↓0w↓0=u↓0$.

\ansno 20. (a) $\sum (αu↓j - u↓{j-1})(\=α
{\=u}↓j - {\=u}↓{j-1}) = \sum (u↓j - \=αu↓{j-1})({\=u}↓j
- α{\=u}↓{j-1})$.\xskip (b) We may assume that $u↓0 ≠ 0$. Let
$m(u) = \prod↓{1≤j≤n} \min(1, |α↓j|) = u↓0/M(u)u↓n$. Whenever
$|α↓j| < 1$, change the factor $x - α↓j$ to ${\=α}↓jx -
1$ in $u(x)$; this doesn't affect $|u|$. Now looking at the
leading and trailing coefficients only, we have $|u|↑2 ≥ |u↓n|↑2m(u)↑2
+ |u↓n|↑2M(u)↑2$; hence we obtain the slightly stronger result
$M(u)↑2 ≤ \biglp |u|↑2 + (|u|↑4 - 4|u↓0u↓n|↑2)↑{1/2}\bigrp
/2|u↓n|↑2$.\xskip (c) $u↓j = u↓m \sum α↓{i↓1}\ldotsm α↓{i↓{m-j}}$,
an elementary symmetric function, hence
$|u↓j| ≤ |u↓m| \sum β↓{i↓1} \ldotsm β↓{i↓{m-j}}$
where $β↓i = \max(1, |α↓i|)$. We complete the proof by showing
that when $x↓1≥1$, $\ldotss$, $x↓n≥1$, and $x↓1 \ldotsm x↓n = M$,
the elementary symmetric function $\sigma ↓{nk} = \sum x↓{i↓1}
\ldotsm x↓{i↓k}$ is $≤{n-1\choose k-1}M + {n-1\choose k}$,
the value assumed when $x↓1 = \cdots = x↓{n-1} = 1$ and $x↓n
= M$.\xskip$\biglp$For if $x↓1 ≤ \cdots ≤ x↓n < M$, the transformation $x↓n
← x↓{n-1}x↓n$, $x↓{n-1} ← 1$ increases $\sigma ↓{nk}$ by $\sigma
↓{(n-2)(k-1)}(x↓n - 1)(x↓{n-1} - 1) > 0$.$\bigrp$\xskip (d) $|v↓j| ≤ |v↓m|
\mathopen{\vcenter{\hjust{\:@\char'0}}}{m-1\choose j}M(v)+
{m-1\choose j-1}\mathclose{\vcenter{\hjust{\:@\char'1}}}≤|u↓n|
\mathopen{\vcenter{\hjust{\:@\char'0}}}{m-1\choose j}M(u)+
{m-1\choose j-1}\mathclose{\vcenter{\hjust{\:@\char'1}}}$
since $|v↓m| ≤ |u↓n|$ and
$M(v) ≤ M(u)$.\xskip [These results are slight extensions of inequalities
due to M. Mignotte, {\sl Math.\ Comp.\ \bf 28} (1974), 1153--1157. See also
J. Vicente Gon\c calves, {\sl Revista de Faculdade de Ci\A encias} (2) A
{\bf1} (Univ. Lisbon, 1950), 167--171.]

\ansno 21. (a) $\int↑{1}↓{0}\biglp u↓ne(n\theta ) + \cdots + u↓0)({\=u}↓n
e(-n\theta ) + \cdots + {\=u}↓0)\,d\theta = |u↓n|↑2 +
\cdots + |u↓0|↑2$ since $\int ↑{1}↓{0} e(j\theta )e(-k\theta
)\,d\theta = \delta↓{jk}$; now use induction on $t$.\xskip (b) Since
$|v↓j| ≤ {m\choose j}M(v)|v↓m|$ we conclude that $|v|↑2 ≤ {2m\choose
m}M(v)↑2|v↓m|↑2$. Hence $|v|↑2|w|↑2 ≤ {2m\choose m}{2k\choose
k}M(v)↑2M(w)↑2|v↓mw↓k|↑2 = f(m, k)M(u)↑2|u↓n|↑2 ≤ f(m, k)|u|↑2$.\xskip
[Slightly better values for $f(m, k)$ are possible based on
the more detailed information in exercise 20.]\xskip (c) The case
$t = 3$ suffices to show how to get from $t - 1$ to $t$. When
$t = 2$ we have shown that, for all $\theta ↓1$, $$\twoline{\textstyle\int ↑{1}↓{0}
\int ↑{1}↓{0} \int ↑{1}↓{0} \int ↑{1}↓{0}\left|v\biglp e(\theta
↓1), e(\phi ↓2), e(\phi ↓3)\bigrp\right|↑2\left|w\biglp e(\theta ↓1),
e(\psi ↓2), e(\psi ↓3)\bigrp \right|↑2\,d\phi ↓2\,d\phi ↓3\,d\psi ↓2\,
d\psi ↓3}{3pt}{\textstyle≤ f(m↓2, k↓2)f(m↓3, k↓3) \int ↑{1}↓{0} \int ↑{1}↓{0}
\left|v\biglp e(\theta ↓1), e(\theta ↓2), e(\theta ↓3)\bigrp \right|↑2
\left|w\biglp e(\theta ↓1), e(\theta ↓2), e(\theta ↓3)\bigrp \right|↑2
\,d\theta ↓2\,d\theta ↓3.}$$ For all $\phi ↓2$, $\phi ↓3$, $\psi ↓2$,
$\psi ↓3$ we have also shown that$$\twoline{\textstyle\int ↑{1}↓{0} \int ↑{1}↓{0}
\left|v\biglp e(\phi ↓1), e(\phi ↓2), e(\phi ↓3)\bigrp \right|↑2\left|w\biglp
e(\psi ↓1), e(\psi ↓2), e(\psi ↓3)\bigrp \right|↑2\,d\phi ↓1\,d\psi
↓1}{3pt}{\textstyle≤ f(m↓1, k↓1) \int ↑{1}↓{0}\left|v\biglp e(\theta ↓1), e(\phi
↓2), e(\phi ↓3)\bigrp \right|↑2\left|w\biglp e(\theta ↓1), e(\psi ↓2),
e(\psi ↓3)\bigrp \right|↑2\, d\theta ↓1.}$$Integrate the former inequality
with respect to $\theta ↓1$ and the latter with respect to $\phi
↓2$, $\phi ↓3$, $\psi ↓2$, $\psi ↓3$.\xskip [This method was used by A.
O. Gel'fond in {\sl Transcendental and Algebraic Numbers} (New
York: Dover, 1960), Section 3.4, to derive a slightly different
result.]

\def\\{\hjust{deg}}
\ansno 22. More generally, assume that $u(x) ≡ v(x)w(x)\modulo
q$, $a(x)v(x) + b(x)w(x) ≡ 1 \modulo p$, and $c\lscr(v) ≡ 1
\modulo r$, $\\(a) < \\(w)$, $\\(h) < \\(v)$, $\\(u)
= \\(v) + \\(w)$, where $r = \gcd(p, q)$ and $p, q$ needn't
be prime. We shall construct polynomials $V(x) ≡ v(x)$ and $W(x)
≡ w(x) \modulo q$ such that $u(x) ≡ V(x)W(x) \modulo {qr}$,
$\lscr(V) = \lscr(v)$, $\\(V) = \\(v)$ $\\(W) =\\(w)$; furthermore,
if $r$ is prime, the results will be unique modulo $qr$.

The problem asks us to find $\=v(x)$ and
$\=w(x)$ with $V(x) = v(x) + q\=v(x)$, $W(x)
= w(x) + q\=w(x)$, $\\(\=v) < \\(v)$, $\\(\=w)≤
\\(w)$; and the other condition $\biglp v(x) + q\=v
(x)\bigrp\biglp w(x) + q\=w(x)\bigrp ≡ u(x)\modulo
{qr}$ is equivalent to $\=w(x)v(x) + \=v(x)w(x)
≡ f(x)\modulo r$, where $u(x) ≡ v(x)w(x) + qf(x) \modulo
{qr}$. We have $\biglp a(x)f(x) + t(x)w(x)\bigrp v(x) + \biglp
b(x)f(x) - t(x)v(x)\bigrp w(x) ≡ f(x) \modulo r$ for all
$t(x)$. Since $\lscr(v)$ has an inverse modulo $r$, we can find
a quotient $t(x)$ by Algorithm 4.6.1D such that $\\(bf - tv)
< \\(v)$; for this $t(x)$, $\\(af + tw) ≤ \\(w)$, since
$\\(f) ≤ \\(u) = \\(v) + \\(w)$. Thus the desired
solution is $\=v(x) = b(x)f(x) - t(x)v(x) = b(x)f(x)\mod
v(x)$, $\=w(x) = a(x)f(x) + t(x)w(x)$. If $\biglp \={\=v}
(x), \={\=w}(x)\bigrp$ is another
solution, we have $\biglp \=w(x) - \={\=w}(x)\bigrp
v(x) ≡ \biglp \={\=v}(x) - \=v(x)\bigrp w(x)
\modulo r$. Thus if $r$ is prime, $v(x)$ must divide $\={\=v}
(x) - \=v(x)$; but $\\(\={\=v}
- \=v) < \\(v)$, so $\={\=v}(x) = 
\=v(x)$ and $\={\=w}(x) = \=w(x)$.

For $p = 2$, the factorization proceeds as follows
(writing only the coefficients, and using bars for negative
digits): Exercise 10 says that $v↓1(x) = (\overline1\,\overline
1\,\overline1)$, $w↓1(x) = (\overline1\,\overline1\,\overline1\,
0\,0\,\overline1\,\overline1)$ in one-bit two's complement notation.
Euclid's extended algorithm yields $a(x) = (1\,0\,0\,0\,0\,1), b(x)
= (1\,0)$. The factor $v(x) = x↑2 + c↓1x + c↓0$ must have $|c↓1|
≤ \lfloor 1 + \sqrt{113}\rfloor = 11$, $|c↓0| ≤ 10$, by exercise
20. Three applications of Hensel's lemma yield $v↓4(x) = (1\,
3\,\overline1)$, $w↓4(x) = (1\,\overline3\,\overline5\,\overline4\,
4\,\overline3\,5)$. Thus $c↓1 ≡ 3$ and $c↓0 ≡ -1\modulo {16}$;
the only possible quadratic factor of $u(x)$ is $x↑2 + 3x -
1$. Division fails, so $u(x)$ is irreducible.\xskip$\biglp$Since we have
now proved the irreducibility of this beloved polynomial by
four separate methods, it is unlikely that it has any factors.$\bigrp$

Hans Zassenhaus has observed that we can often
speed up such calculations by increasing $p$ as well as $q$:
In the above notation, we can find $A(x)$, $B(x)$ such that $A(x)V(x)
+ B(x)W(x) ≡ 1 \modulo {pr}$, namely by taking $A(x) = a(x)
+ p\=a(x)$, $B(x) = b(x) + p\=b(x)$, where $\=a
a(x)V(x) + \=b(x)W(x) ≡ g(x)\modulo r$, $a(x)V(x)
+ b(x)W(x) ≡ 1 - pg(x) \modulo {pr}$. We can also find $C$
with $\lscr(V)C ≡ 1\modulo {pr}$. In this way we can lift a
squarefree factorization $u(x) ≡ v(x)w(x) \modulo p$ to its
unique extensions modulo $p↑2$, $p↑4$, $p↑8$, $p↑{16}$, etc. However,
this ``accelerated'' procedure reaches a point of diminishing
returns in practice, as soon as we get to double-precision moduli,
since the time for multiplying multiprecision numbers in practical
ranges outweighs the advantage of squaring the modulus directly.
From a computational standpoint it seems best to work with the
successive moduli $p$, $p↑2$, $p↑4$, $p↑8$, $\ldotss$, $p↑E$, $p↑{E+e}$,
$p↑{E+2e}$, $p↑{E+3e}$, $\ldotss $, where $E$ is the smallest power
of 2 with $p↑E$ greater than single precision and $e$ is the
largest integer such that $p↑e$ has single precision.

Hensel's lemma, which he introduced in order to
demonstrate the factorization of polynomials over the field
of $p$-adic numbers (see exercise 4.1--31), can be generalized
in several ways. First, if there are more factors, say $u(x)
≡ v↓1(x)v↓2(x)v↓3(x) \modulo p$, we can find $a↓1(x)$, $a↓2(x)$,
$a↓3(x)$ such that $a↓1(x)v↓2(x)v↓3(x) + a↓2(x)v↓1(x)v↓3(x) +
a↓3(x)v↓1(x)v↓2(x) ≡ 1 \modulo p$, $\\(a↓i) < \\(v↓i)$.\xskip
$\biglp$In essence, $1/u(x)$ is expanded in partial fractions as $\sum
a↓i(x)/v↓i(x)$.$\bigrp$\xskip An exactly analogous construction now allows
us to lift the factorization without changing the leading coefficients
of $v↓1$ and $v↓2$; we take $\=v↓1(x) = a↓1(x)f(x)\mod
v↓1(x)$, $\=v↓2(x) = a↓2(x)f(x)\mod v↓2(x)$, etc. Another
important generalization is to several simultaneous moduli,
of the respective forms $p↑e$, $(x↓2 - a↓2)↑{n↓2}$, $\ldotss
$, $(x↓t - a↓t)↑{n↓t}$, when performing multivariate gcds
and factorizations. Cf.\ D. Y. Y. Yun, Ph.D. Thesis (M.I.T.,
1974).

\ansno 23. The discriminant of pp$\biglp u(x)\bigrp$ is a nonzero integer (cf.\
exercise 4.6.1--12), and there are multiple factors modulo $p$
iff $p$ divides the discriminant.\xskip$\biglp$The factorization of (21)
modulo 3 is $(x + 1)(x↑2 - x - 1)↑2(x↑3 + x↑2 - x + 1)$; squared
factors for this polynomial occur only for $p = 3$, 23, 233
and 121702457. It is not difficult to prove that the smallest
prime that is not unlucky is at most $O(n\log Nn)$, if $n
= \\(u)$ and $N$ bounds the coefficients of $u(x)$.$\bigrp$

%folio 818 galley 4a (C) Addison-Wesley 1978	*
\ansno 24. Multiply a monic polynomial with rational coefficients
by a suitable nonzero integer, to get a primitive polynomial
over the integers. Factor this polynomial over the integers,
and then convert the factors back to monic.\xskip (No factorizations
are lost in this way; see exercise 4.6.1--8.)

\ansno 25. Consideration of the constant term shows there are
no factors of degree 1, so if the polynomial is reducible, it
must have one factor of degree 2 and one of degree 3. Modulo
2 the factors are $x(x + 1)↑2(x↑2+x+1)$; this is not much help.
Modulo 3 the factors are $(x + 2)↑2(x↑3+2x+2)$. Modulo 5 they
are $(x↑2 + x + 1)(x↑3 + 4x + 2)$. So we see that the answer
is $(x↑2 + x + 1)(x↑3 - x + 2)$.

\ansno 26. Begin with $D ← (0 \ldotsm 0 1)$, representing the
set $\{0\}$. Then for $1 ≤ j ≤ r$, set $D ← D ∨ (D\lsh d↓j)$,
where $∨$ denotes logical ``or'' and $D\lsh d$ denotes $D$ shifted left
$d$ bit positions.\xskip$\biglp$Actually we need only work with a bit
vector of length $\lceil(n + 1)/2\rceil$, since $n - m$ is in the set iff
$m$ is.$\bigrp$

\ansno 27. Exercise 4 says that a random polynomial of degree
$n$ is irreducible modulo $p$ with rather low probability, about
$1/n$. But the Chinese remainder theorem implies that a random
monic polynomial of degree $n$ over the integers will be reducible
with respect to each of $k$ distinct primes with probability
about $(1 - 1/n)↑k$, and this approaches zero as $k → ∞$. Hence
almost all polynomials over the integers are irreducible with
respect to infinitely many primes; and almost all primitive
polynomials over the integers are irreducible.\xskip [Another proof
has been given by W. S. Brown, {\sl AMM \bf 70} (1963), 965--969. See
also the generalization cited in the answer to exercise 33.]

\def\\{\hjust{deg}}
\ansno 28. False, we lose all $p↓j$ with $e↓j$ divisible by
$p$. True if $p ≥ \\(u)$.

\ansno 29. Compute $V↓1(x) = \gcd\biglp v(x), v↑\prime (x)\bigrp$;
this is legitimate since $v↓1(x)$ is relatively prime to $v↑\prime
(x)/v↓1(x)$. Let $v↓0(x) = v(x)/v↓1(x)$, the (squarefree) product
of all irreducible factors of $v(x)$. Compute $d↓1(x) = \gcd\biglp
u(x), v↓0(x)\bigrp$ and $u↓1(x) = u(x)/d↓1(x)$. If $\\(d↓j)
> 0$ for $j ≥ 1$, compute $\=d↓{j+1}(x) = \gcd\biglp
d↓j(x), v↓j(x)\bigrp$, $d↓{j+1}(x) = \gcd\biglp \=d↓{j+1}(x),
u↓j(x)\bigrp$, $v↓{j+1}(x) = v↓j(x)/\=d↓{j+1}(x)$, $u↓{j+1}(x)
= u↓j(x)/d↓{j+1}(x)$; but if deg$(d↓1) = 0$, terminate
the computation with the answer $d(x) = d↓1(x) \ldotsm d↓j(x)$.\xskip
$\biglp$ In this method, $d↓j(x)$ is the squarefree product of
all irreducible factors that occur $≥j$ times in $\gcd\biglp
u(x), v(x)\bigrp$. There are several ways to avoid redundant
calculations; for example, the same $p$ can be used in the underlying
gcd computations, and the gcd routine should return the values
of $u(x)/d(x)$ and $v(x)/d(x)$ that it computes. Furthermore
the computation is unsymmetric in $u$ and $v$; it seems better
to interchange the r\A oles of $u$ and $v$ if $\\(u)>\\(v)$
at the beginning or if $\\(u↓j) >\\(v↓j)$ when
computing $d↓{j+1}(x)$.$\bigrp$

 \ansno 30. Cf.\ exercise 4; the probability is the coefficient
of $z↑n$ in ${(1+a↓{1p}z/p)}\*
{(1 + a↓{2p}z↑2/p↑2)}\*{(1 + a↓{3p}z↑3/p↑3)}\ldotsm $, which has the
limiting value $g(z) = {(1 + z)}\*{(1 + {1\over 2}z↑2)}\*
{(1 + {1\over 3}z↑3)}\ldotsm\,$. For $1 ≤ n ≤ 10$ the answers are 1, ${1\over
2}$, ${5\over 6}$, ${7\over 12}$, ${37\over 60}$, ${79\over
120}$, ${173\over 280}$, ${101\over 168}$, ${127\over 210}$, ${1033\over
1680}$.\xskip$\biglp$Let
$f(y) = \ln(1 + y) - y = O(y↑2)$. We have $$\textstyle g(z) = \exp\biglp \sum
↓{n≥1} z↑n/n + \sum ↓{n≥1} f(z↑n/n)\bigrp =
h(z)/(1 - z),$$ and it can be shown that the limiting probability
is $h(1) =
\exp\biglp \sum ↓{n≥1} f(1/n)\bigrp =e↑{-\gamma}\approx .56146$
as $n → ∞$ [cf.\ D. H. Lehmer, {\sl Acta Arith.\ \bf 21} (1972),
379--388].\xskip Indeed, N. G. de Bruijn has established the asymptotic
formula $\lim↓{p→∞} a↓{np} =
e↑{-\gamma}+ e↑{-\gamma}/n + O(n↑{-2}\log n)$.$\bigrp$

\ansno 31. One can do arithmetic in a field $F$ of $p↑d$ elements by letting the
elements of $F$ be polynomials $s(y)$, modulo $p$ and modulo any given
irreducible polynomial $q(y)$ of degree $d$. Since every irreducible factor
$h(x)$ of $g(x)$ is a divisor of $x↑{p↑d}-x=\prod\leftset s-s(y)\relv
s(y)\in F\rightset$, $h(x)$ must have {\sl linear} factors when regarded as
a polynomial over $F$. If $h\biglp s(y)\bigrp=0$ then also $h\biglp s(y)↑p\bigrp
=0$ and $s(y)↑{p↑k}≠s(y)$ for $1≤k<d$; hence the complete factorization of
$h(x)$ is $\biglp x-s(y)\bigrp\biglp x-s(y)↑p\bigrp\ldotsm\biglp x-s(y)↑{p↑{d-1}}
\bigrp$.

To find a factor of $g(x)$, find a root $s(y)$ of $g(x)$, working in $F$, and
compute $h(x)$ by evaluating the above product. To find a root $s(y)$ of
$g(x)$ over $F$, note that $\gcd\biglp w(x),\,(x+t(y))↑{(p↑d-1)/2}-1\bigrp$
will be a nontrivial factor of $w(x)$ at least about half of the time, whenever
$w(x)$ has nothing but linear factors over $F$, as in exercise 14. Thus,
start with $w(x)=g(x)$ and find a nontrivial factor $f(x)$ over $F$; then
replace $w(x)$ by $f(x)$ or by $w(x)/f(x)$, whichever has smaller degree,
and repeat until $w(x)$ has degree 1.

[A similar procedure can be used when $p=2$: In this case $\gcd\biglp w(x),\,
T(t(y)x)\bigrp$ will be a nontrivial factor of $w(x)$ at least half of the time,
whenever $w(x)$ has nothing but linear factors over $F$, where $T(x)=
x+x↑2+x↑4+\cdots+x↑{2↑{d-1}}$. For exactly half of the elements $s(y)$ of
$F$ satisfy $T\biglp s(y)\bigrp=0$, and $T\biglp s↓1(y)t(y)\bigrp=
T\biglp s↓2(y)t(y)\bigrp$ iff $T\biglp(s↓1(y)-s↓2(y))t(y)\bigrp=0$.]

\def\+{\hjust{$\Psi$\hskip-1.5pt}}
\ansno 32. (a) Clearly $x↑n-1=\prod↓{d\rslash n}\+↓d(x)$, since every complex
$n$th root of unity is a primitive $d$th root for some unique $d\rslash n$.
The second identity follows from the first; and $\+↓n(x)$ has integer
coefficients since it is expressed in terms of products and quotients of monic
polynomials with integer coefficients.\xskip(b) The condition in the hint
suffices to prove that $f(x)=\+↓n(x)$, so we shall take the hint. When
$p$ does not divide $n$, we have $\gcd(x↑n-1,nx↑{n-1})=1$ modulo $p$, hence
$x↑n-1$ is squarefree modulo $p$. Given $f(x)$ and $\zeta$ as in the hint,
let $g(x)$ be the irreducible factor of $\+↓n(x)$ such that $g(\zeta↑p)=0$.
If $g(x)≠f(x)$ then both $f(x)$ and $g(x)$ are distinct factors of $\+↓n(x)$,
hence they are distinct factors of $x↑n-1$, hence they have no irreducible
factors in common modulo $p$. However, $\zeta↑p$ is a root of $f(x↑p)$,
so $\gcd\biglp g(x),f(x↑p)\bigrp≠1$ over the integers, hence $g(x)$ is
a divisor of $f(x↑p)$. By (5), $g(x)$ is a divisor of $f(x)↑p$, modulo $p$,
contradicting the assumption that $f(x)$ and $g(x)$ have no irreducible
factors in common. Therefore $f(x)=g(x)$.\xskip[The irreducibility of
$\+↓n(x)$ was first proved for prime $n$ by K. F. Gauss in {\sl Disquisitiones
Arithmetic\ae\ }(Leipzig, 1801), Art.\ 341, and for general $n$ by L.
Kronecker, {\sl J. de Math. Pures et Appliqu\'ees \bf19} (1854), 177--192.]

(c) $\+↓1(x)=x-1$; and when $p$ is prime, $\+↓p(x)=1+x+\cdots+x↑{p-1}$.
If $n>1$ is odd, it is not difficult to prove that $\+↓{2n}(x)=\+↓n(-x)$.
If $p$ divides $n$, the second identity in (a) shows that $\+↓{pn}(x)=
\+↓n(x↑p)$. If $p$ does not divide $n$, we have $\+↓{pn}(x)=\+↓n(x↑p)/
\+↓n(x)$. For nonprime $n≤15$ we have $\+↓4(x)=x↑2+1$, $\+↓6(x)=
x↑2-x+1$, $\+↓8(x)=x↑4+1$, $\+↓p(x)=x↑6+x↑3+1$, $\+↓{10}(x)=
x↑4-x↑3+x↑2-x+1$, $\+↓{14}(x)=x↑6-x↑5+x↑4-x↑3+x↑2-x+1$, $\+↓{15}(x)=
x↑8-x↑7+x↑5-x↑4+x↑3-x+1$.\xskip[The formula $\+↓{pq}(x)=(1+x↑p+\cdots+x↑{(q-1)p})
(x-1)/(x↑q-1)$ can be used to show that $\+↓{pq}(x)$ has all coefficients
$\pm1$ or 0 when $p$ and $q$ are prime; but the coefficients of $\+↓{pqr}(x)$
can be arbitrarily large.]

\ansno 33. The exact probability is $\prod↓{j≥1}(a↓{jp}/p↑j)↑{k↓j}/k↓j!$,
where $k↓j$ is the number of $d↓i$ equal to $j$. Since $a↓{jp}\approx 1/j$
by exercise 4, we get the formula of exercise 1.3.3--21.

{\sl Notes:} This exercise says that if we fix the prime $p$ and let the
polynomial $u(x)$ be random, it will have certain probability of splitting
in a given way modulo $p$. A much harder problem is to fix the polynomial $u(x)$
and to let $p$ be ``random''; but the same asymptotic result holds
for almost all $u(x)$:\xskip G. Frobenius proved in 1880 that the integer
polynomial $u(x)$ splits modulo $p$ into factors of degrees $d↓1$, $\ldotss$, $d↓r$,
when $p$ is a large prime chosen at random, with probability equal to the
number of permutations in the Galois group $G$ of $u(x)$ having cycle lengths
$\{d↓1,\ldotss,d↓k\}$ divided by the total number of permutations in $G$.\xskip
[If $u(x)$ has rational coefficients and distinct roots $\xi↓1$, $\ldotss$,
$\xi↓n$ over the complex numbers, its Galois group is the (unique) group $G$
of permutations such that the polynomial $\prod↓{p(1)\ldotsm p(n)\in G}
\biglp z+\xi↓{p(1)}y↓1+\cdots+\xi↓{p(n)}y↓n\bigrp=U(z,y↓1,\ldotss,y↓n)$ has rational
coefficients and is irreducible over the rationals.]\xskip Furthermore
B. L. van der Waerden proved in 1934 that almost all polynomials of degree $n$
have the set of all $n!$ permutations as their Galois group. Therefore
almost all fixed irreducible polynomials $u(x)$ will factor as we might expect them
to, with respect to randomly chosen large primes $p$.\xskip References:
{\sl Sitzungsberichte K\"onigl.\ Preu\ss.\ Akad.\ Wiss.\ }(Berlin, 1896),
\hjust{689--703}; {\sl Math.\ Annalen \bf109} (1934), 13--16.